#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 100
typedef enum { FALSE, TRUE } Boolean;
typedef struct {
	char vertex[MaxVertexNum];
	int edge[MaxVertexNum][MaxVertexNum];
} MGraph;
int locate_vertex(MGraph* G, char vertex_name) {
	int i;
	for (i = 0; i < 8; i++)
		if (G->vertex[i] == vertex_name)
			return i;
	return -1;
}
void create_graph(MGraph** G_pp, char* graph_data_filename)
{
	FILE* fp;
	size_t len = 0;
	size_t read;
	int num_nodes, num_edges;
	fp = fopen(graph_data_filename, "r");
	if (fp == NULL)
		exit(EXIT_FAILURE);
	fscanf(fp, "%d %d\n", &num_nodes, &num_edges);
	printf("节点数为:%d\n边数为:%d\n", num_nodes, num_edges);
	int j, h;
	(*G_pp) = (MGraph*)malloc(sizeof(MGraph));
	MGraph* gpp = *G_pp;
	for (j = 0; j < num_nodes; j++) {
		gpp->vertex[j] = fgetc(fp);
		fgetc(fp);
		printf("%c ", gpp->vertex[j]);
	}
	printf("\n");
	for (j = 0; j < num_nodes; j++) {
		for (h = 0; h < num_nodes; h++) {
			gpp->edge[j][h] = 0;
		}
	}
	char v1, v2;
	for (int k = 0; k < num_edges; k++) {
		v1 = fgetc(fp);
		printf("%c", v1);
		fgetc(fp);
		v2 = fgetc(fp);
		fgetc(fp);
		printf("%c\n", v2);
		for (j = 0; j < num_nodes; j++) {
			for (h = 0; h < num_nodes; h++) {
				if (gpp->vertex[h] == v2 && gpp->vertex[j] == v1) {
					gpp->edge[j][h] = 1;
					gpp->edge[h][j] = 1;
				}
			}
		}
	}
	printf("邻接矩阵如下：\n");
	for (j = 0; j < num_edges; j++) {
		for (h = 0; h < num_edges; h++) {
			printf("%d\t", gpp->edge[j][h]);
		}
		printf("\n");
	}
	fclose(fp);
}
void dfs(MGraph* G, int i, Boolean visited[], char* result_sequence, int* visited_order)
{
	int j;
	result_sequence[*visited_order] = G->vertex[i];
	(*visited_order)++;
	visited[i] = TRUE;
	for (j = 0; j < 8; j++) {
		if (G->edge[i][j] == 1 && !visited[j]) {
			dfs(G, j, visited, result_sequence, visited_order);
		}
	}
	
}
void bfs(MGraph* G, int k, Boolean visited[], char* visited_sequence) {
	int i, j = 0, r = 0, f = 0;
	char dl[MaxVertexNum];
	for (i = 0; i < MaxVertexNum; i++) {
		visited[i] = FALSE;
		visited_sequence[i] = 0;
		dl[i] = 0;
	}
	dl[r] = G->vertex[k];
	visited[k] = TRUE;
	while (dl[r] != 0) {
		for (i = 0; i < 8; i++) {
			if (G->edge[k][i] == 1 && visited[i] == FALSE) {
				f++;
				visited[i] = TRUE;
				dl[f] = G->vertex[i];
			}
		}
		visited_sequence[j] = dl[r];
		r++;
		k = locate_vertex(G, dl[r]);
		j++;
	}
}
void main() {
	int i;
	MGraph* G;
	Boolean visited[MaxVertexNum];
	
	for (i = 0; i < MaxVertexNum; i++) {
		visited[i] = FALSE;
	}
	create_graph(&G, "graph_data.txt");
	char dfs_sequence[MaxVertexNum] = { '\0' };
	int visited_order = 0;
	dfs(G, 0, visited, dfs_sequence, &visited_order);
	printf("Print Graph DFS: ");
	printf("%s\n", dfs_sequence);
	printf("\n");
	for (i = 0; i < MaxVertexNum; i++) {
		visited[i] = FALSE;
	}
	char bfs_sequence[MaxVertexNum] = { '\0' };
	bfs(G, 0, visited, bfs_sequence);
	printf("Print Graph BFS: ");
	printf("%s\n", bfs_sequence);
	char bfs_sequence2[MaxVertexNum] = { '\0' };
	bfs(G, 3, visited, bfs_sequence2);
	printf("Print Graph BFS: ");
	printf("%s\n", bfs_sequence2);
}